// 题目描述
// LCR 014. 字符串的排列
// 中等
// 101
// 给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的某个变位词。
// 换句话说，第一个字符串的排列之一是第二个字符串的 子串 。
//   示例 1：
// 输入: s1 = "ab" s2 = "eidbaooo"
// 输出: True
// 解释: s2 包含 s1 的排列之一 ("ba").
// 示例 2：
// 输入: s1= "ab" s2 = "eidboaoo"
// 输出: False
//   提示：
// 1 <= s1.length, s2.length <= 104
// s1 和 s2 仅包含小写字母
//   注意：本题与主站 567 题相同： https://leetcode-cn.com/problems/permutation-in-string/
// 通过次数
// 45.9K
// 提交次数
// 89.2K
// 通过率
// 51.4%
// https://leetcode.cn/problems/MPnaiL

/**
 * @param {string} s1
 * @param {string} s2
 * @return {boolean}
 */
var checkInclusion = function (s1, s2) {
  const needs = new Map()
  for (const ch of s1) {
    needs.set(ch, (needs.get(ch) || 0) + 1)
  }
  const win = new Map()

  let left = 0, right = 0, valid = 0
  while (right < s2.length) {
    // 初始窗口内不是子串
    const ch = s2[right++]
    // ！！！判断异位词的固定套路，维护一个 valid 变量
    if (needs.has(ch)) {
      win.set(ch, (win.get(ch) || 0) + 1)
      if (win.get(ch) === needs.get(ch)) {
        ++valid
      }
    }

    // 窗口收缩条件为：窗口内是子串
    while (right - left === s1.length) {
      // ！！！当 valid === needs.size 时，窗口内是异位词
      if (valid === needs.size) {
        return true
      }

      const last = s2[left++]
      if (needs.has(last)) {
        if (win.get(last) === needs.get(last)) {
          --valid
        }
        win.set(last, (win.get(last) || 0) - 1)
      }
    }
  }

  return false
}

console.log(
  checkInclusion(
    "abc",
    "ccccbbbbaaaa"
  )
)
